#include "bruteforce.h"

static bool bit_is_set(int num, int bit) {
	return (num >> bit) & 0x1;
}


int BruteForce(DataSet &ds) {
	if (ds.n <= 25) {
		int max, sum, cnt, cur, roof;

		max = 0;
		roof = 1 << ds.n;
		for (cnt = 1; cnt < roof; ++cnt) {
			sum = 0;
			for (cur = 0; cur < ds.n; ++cur)
				if (bit_is_set(cnt, cur))
					sum += ds.nums[cur];

			if (sum <= ds.u && sum > max)
				 max = sum;
		}

		return max;
	} else
		return -1;
}